package tree;

import java.util.Arrays;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-06-25 23:19
 */
public class T99_recoverTree {
    public void recoverTree(TreeNode root) {
        //记录错误的两个值
        TreeNode x = null, y = null;
        //记录中序遍历当前节点的前驱
        TreeNode pre = null;
        //用来完成Morris连接的寻找前驱的指针
        TreeNode predecessor = null;
        while (root != null) {
            if (root.left != null) {//左子树不为空，1、链接root节点的前驱，他的前驱还没访问，所以root不能现在访问,继续访问root左子树  2、root节点访问,并且断开root节点的前驱连接，然后访问root的右子树
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == root) {//说明了1已经执行过了，我们执行2
                    //访问
                    if (pre != null && pre.val > root.val) {
                        if (x == null) x = pre;
                        y = root;
                    }
                    //更新前驱,为下一个节点做准备
                    pre = root;
                    //断开前驱连接
                    predecessor.right = null;
                    //访问root右子树
                    root = root.right;
                } else {//predecessor.right ！= root,说明了还没执行过1
                    predecessor.right = root;
                    root = root.left;
                }
            } else {
                //root.left == null，root不需要链接节点的前驱（他的前驱其实就是pre(第一个节点pre为null)，且已经被访问过了），
                // 那么直接访问root
                //访问

                // 该结点没有左孩子,说明是某个根结点的右子树的最左孩子结点
                // (也有可能它就是最左的结点，这时它的前驱结点pre为null)
                if (pre != null && pre.val > root.val) {
                    if (x == null) x = pre;
                    y = root;
                }
                //更新前驱,为下一个节点做准备
                pre = root;
                //访问root的右子树
                root = root.right;
            }
        }
        swap(x, y);
    }

    public void swap(TreeNode x, TreeNode y) {
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }



}
